package leetcode.code1240;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution implements IDebug {

	int ans, m, n;

	int INF = 13 * 13;

	public int tilingRectangle(int n, int m) {
		ans = INF;
		this.m = m;
		this.n = n;
		int[][] grid = new int[m][n];
		f(grid, 0);
		return ans;
	}

	private void f(int[][] grid, int find) {
		// 剪枝
		if (find > ans) {
			return;
		}
		boolean done = true;
		int x = 0, y = 0;
		// 检查所有位置是否被盖住了
		for (int i = 0; i < m && done; i++) {
			for (int j = 0; j < n; j++) {
				if (grid[i][j] == 0) {
					done = false;
					x = i;
					y = j;
					break;
				}
			}
		}
		if (done) {
			ans = Math.min(find, ans);
			return;
		}
		for (int k = Math.min(m - x, n - y); k >= 1; k--) {
			boolean ok = true;
			// x,y开始的k方形中没有1
			for (int i = x; i < x + k && ok; i++) {
				for (int j = y; j < y + k; j++) {
					if (grid[i][j] == 1) {
						ok = false;
						break;
					}
				}
			}
			if (ok) {
				// 用1给这个k方形改上
				for (int i = x; i < x + k; i++) {
					for (int j = y; j < y + k; j++) {
						grid[i][j] = 1;
					}
				}
				// 继续尝试
				f(grid, find + 1);
				// 回溯
				for (int i = x; i < x + k; i++) {
					for (int j = y; j < y + k; j++) {
						grid[i][j] = 0;
					}
				}
			}
		}
	}

	@Override
	public void debug4() {
		H.compare(3, this.tilingRectangle(2, 3));
		H.compare(5, this.tilingRectangle(5, 8));
		H.compare(6, this.tilingRectangle(11, 13));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
	}

}
